/*
 * Fernanda Ibarrola - 0711920
 * Luiza Silva       - 0810905
 *
 */


#include <stdio.h>
#include <stdlib.h>

#include "heap.h"

#define INIT_ALLOC 6

struct heap {
	void** vetor;
	int tamanho;
	int qtdElementos;
	int (*cmpFunc)(void*, void*);
};

/* Implementacao das funcoes externadas */

Heap* criarHeap (int (*cmp)(void*, void*))
{
	Heap* novaHeap = (Heap*)malloc(sizeof(Heap));

	if (!novaHeap) {
		printf("Problema na alocacao\n");
		exit(1);
	}

	novaHeap->vetor = NULL;
	novaHeap->tamanho = 0;
	novaHeap->qtdElementos = 0;
	novaHeap->cmpFunc = cmp;

	return novaHeap;
}

void destruirHeap (Heap* h)
{
	if (h->vetor != NULL) {
		free(h->vetor);
	}

	free(h);
}

void adicionarElemento (Heap* h, void* elementoNovo)
{
	int indPai;
	int indNovo;
	void* temp;

	/* essa parte insere o elemento no final da heap,
	realocando o vetor se necessario */	
	
	/* Por uma questao de otimizacao de performance, estou
	usando a mesma regra de alocacao da STL, que e alocar
	sempre o dobro do numero de elementos anterior, com o
	objetivo de diminuir as alocacoes feitas */

	if (h->tamanho == 0) {
		h->vetor = malloc(sizeof(void*)*INIT_ALLOC);

		if (!(h->vetor)) {
			printf("Problema na alocacao\n");
			exit(1);
		}

		h->tamanho = INIT_ALLOC;

		h->vetor[h->qtdElementos] = elementoNovo;
		h->qtdElementos++;
	}

	else {
		if (h->tamanho == h->qtdElementos) {
			h->vetor = realloc(h->vetor, sizeof(void*)*(2*h->tamanho));
			
			if (!(h->vetor)) {
				printf("Problema na alocacao\n");
				exit(1);
			}

			h->tamanho*=2;

			h->vetor[h->qtdElementos] = elementoNovo;
			h->qtdElementos++;
		}
		else {
			h->vetor[h->qtdElementos] = elementoNovo;
			h->qtdElementos++;
		}
	}

	/* essa parte verifica se a insercao esta violando
	a propriedade do heap */


	indNovo = h->qtdElementos-1;
	indPai = (indNovo-1)/2;

	if (indNovo == 0) {
		/* nao ha mais nada a se fazer */
		return;
	}

	while ((*h->cmpFunc)(h->vetor[indNovo], h->vetor[indPai])>0) {
		/* se filho for maior que pai, troca os dois */

		temp = h->vetor[indNovo];
		h->vetor[indNovo] = h->vetor[indPai];
		h->vetor[indPai] = temp;

		indNovo = indPai;
		indPai = (indNovo-1)/2;

		if (indNovo == 0) {
			/* nao ha mais nada a se fazer */
			return;
		}
	}	
} 

void tirarElemento (Heap* h)
{
	int pai, esq, dir, swap, largest;
	void* temp;
	
	if (!h->qtdElementos)
		return;

	h->vetor[0] = h->vetor[h->qtdElementos-1];

	h->qtdElementos--;

	if ((h->qtdElementos <= h->tamanho/2) && (h->tamanho>6)) {
		/* vamos desalocar 1/3 do vetor, por otimizacao de espaco,
		novamente seguindo a implementacao utilizada na STL */
		
		h->vetor = realloc(h->vetor, sizeof(void*)*(2*(h->tamanho)/3));
		h->tamanho= 2*(h->tamanho)/3;
	}
	
	pai = 0;
	esq = 1;
	dir = 2;
	swap = 0;
	
	/* Checando validez dos indices */

	if (pai >= h->qtdElementos || esq >= h->qtdElementos) 
		return;

	if ((*h->cmpFunc)(h->vetor[esq], h->vetor[pai]) > 0)
		swap = 1;

	/* Aqui comeca a operacao heapify down */

	while (swap) {
		if (dir >= h->qtdElementos)
			largest = esq;	
		else {
			if ((*h->cmpFunc)(h->vetor[esq], h->vetor[dir]) > 0)
				largest = esq;
			else
				largest = dir;
		}
		
		temp = h->vetor[largest];
		h->vetor[largest] = h->vetor[pai];
		h->vetor[pai] = temp;

		pai = largest;	

		esq = 2*pai+1;
		dir = 2*pai+2;
		
		if (pai >= h->qtdElementos || esq >= h->qtdElementos) 
			break;

		if ((*h->cmpFunc)(h->vetor[esq], h->vetor[pai]) > 0)
			swap = 1;
	}
}

void* retornaTopo (Heap* h)
{
	return h->vetor[0];
}

int tamanhoHeap (Heap* h)
{
	return h->qtdElementos;
}

int heapVazia (Heap* h)
{
	if (!h->qtdElementos)
		return 1;

	return 0;
}

void printHeap (Heap* h, int (*print)(void*))
{
	int i, j;
	int level=0;	
	int elemLevel=0;	
	int lastLevel;	
	int numsp=0;

	for (i=0; i<32; i++) {
		if (h->qtdElementos<(1<<i)) {
			lastLevel = i;
			break;
		}
	}

	lastLevel--;


	for (i=0; i<lastLevel; i++)
		numsp = numsp*2+1;

	for (i=0; i<numsp; i++)
		printf(" ");

	for (i=0; i<h->qtdElementos; i++) {
		if (i > elemLevel) {
			printf("\n");

			numsp--; numsp/=2;
			
			for (j=0; j<numsp; j++)
				printf(" ");			

			
			level++;
			elemLevel+=(1<<level);
		}
		else {
			if (i!=0) {
				for (j=0; j<(2*numsp+1); j++)
					printf(" ");
			}
		}

		(*print)(h->vetor[i]);
	}

	printf("\n");
}
